package middle;

import java.util.ArrayList;
import java.util.List;

public class Solution_236 {
    private TreeNode p, q, rst = null;
    private boolean p_flag, q_flag;
    private List<TreeNode> list_p;
    private List<TreeNode> list_q;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        list_p = new ArrayList<>();
        list_q = new ArrayList<>();
        this.p = p;
        this.q = q;
//        dps(root, new ArrayList<>());
//        TreeNode pre = null;
//        for (int i = 0; i < Math.min(list_p.size(), list_q.size()); i++) {
//            if (list_p.get(i) == list_q.get(i)) {
//                pre = list_p.get(i);
//            }
//        }
//        return pre;
        dps(root);
        return rst;
    }

    private int dps(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int count = (node.val == p.val || node.val == q.val) ? 1 : 0;
        count += dps(node.left);
        if (count < 2) {
            count += dps(node.right);
        }
        if (count == 2 && rst == null) {
            rst = node;
        }
        return count;
    }

    private void dps(TreeNode node, List<TreeNode> list) {
        if (node == null) {
            return;
        }
        list.add(node);
        if (node.val == p.val) {
            list_p = new ArrayList<>(list);
        } else if (node.val == q.val) {
            list_q = new ArrayList<>(list);
        }
        if (list_q.size() == 0 || list_p.size() == 0) {
            dps(node.left, list);
            dps(node.right, list);
        }
        list.remove(list.size() - 1);
    }

    public static void main(String[] args) {
        Solution_236 model = new Solution_236();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);
        root.right = new TreeNode(1);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);
        System.out.println(model.lowestCommonAncestor(root, new TreeNode(5), new TreeNode(4)).val);
    }

    static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
}
